#coding=utf-8
import profile
import random
import datetime
import copy

"""
fib
"""
catch = {0:0,1:1}
def fib(n):
    """
    fib with Recursive and catch
    """
    if catch.has_key(n):
        return catch[n]
    else:
        r = fib(n - 1) + fib(n - 2)
        catch[n] = r
        return r

def fib2(n):
    """
    fib without Recursive
    """
    assert n >= 0 and type(n) == type(1),"n must be unsigned int"
    a,b = 0,1
    while(n >= 1):
        a,b = b,a + b
        n -= 1
    return a


def quickSort(ls):
    """
    quick sort
    """
    return [] if ls == [] else \
            quickSort([x for x in ls[1:] if x < ls[0]]) +\
            [x for x in ls[1:] if x == ls[0]] +\
            quickSort([x for x in ls[1:] if x > ls[0]])

def perfmon(func,data):
    pro_data = copy.deepcopy(data)
    t1 = datetime.datetime.now()
    func(data)
    t2 = datetime.datetime.now()
    print func.__name__,t2-t1

if __name__ == '__main__':
    print fib(986)
    print profile.run("fib(986)")
    print fib2(986)
    print profile.run("fib2(986)")
    
    data = [random.randint(0,65536) for i in xrange(200000)]
    d1 = [9 for i in xrange(200000)]
    perfmon(quickSort,data)
    perfmon(quickSort,d1)
    perfmon(fib2,20000)

